Optimization and Control 16
☆ On the Value Function of Convex Bolza Problems Governed by Stochastic Difference Equations
In this paper we study the value function of Bolza problems governed by stochastic difference equations, with particular emphasis on the convex non-anticipative case. Our goal is to provide some insights on the structure of the subdiferential of the value function. In particular, we establish a connection between the evolution of the subgradients of the value function and a stochastic difference equation of Hamiltonian type. This result can be seen as a transposition of the method of characteristics, introduced by Rockafellar and Wolenski in the 2000s, to the stochastic discrete-time setting. Similarly as done in the literature for the deterministic case, the analysis is based on a duality approach. For this reason we study first a dual representation for the value function in terms of the value function of a dual problem, which is a pseudo Bolza problem. The main difference with the deterministic case is that (due to the non-anticipativity) the symmetry between the Bolza problem and its dual is no longer valid. This in turn implies that ensuring the existence of minimizers for the Bolza problem (which is a key point for establishing the method of characteristics) is not as simple as in the deterministic case, and it should be addressed differently. To complete the exposition, we study the existence of minimizers for a particular class of Bolza problems governed by linear stochastic difference equations, the so-called linear-convex optimal control problems.
☆ ZIVR: An Incremental Variance Reduction Technique For Zeroth-Order Composite Problems
This paper investigates zeroth-order (ZO) finite-sum composite optimization. Recently, variance reduction techniques have been applied to ZO methods to mitigate the non-vanishing variance of 2-point estimators in constrained/composite optimization, yielding improved convergence rates. However, existing ZO variance reduction methods typically involve batch sampling of size at least $Θ(n)$ or $Θ(d)$, which can be computationally prohibitive for large-scale problems. In this work, we propose a general variance reduction framework, Zeroth-Order Incremental Variance Reduction (ZIVR), which supports flexible implementations$\unicode{x2014}$including a pure 2-point zeroth-order algorithm that eliminates the need for large batch sampling. Furthermore, we establish comprehensive convergence guarantees for ZIVR across strongly-convex, convex, and non-convex settings that match their first-order counterparts. Numerical experiments validate the effectiveness of our proposed algorithm.
☆ Stochastic convergence of a class of greedy-type algorithms for Configuration Optimization Problems
Greedy Sampling Methods (GSMs) are widely used to construct approximate solutions of Configuration Optimization Problems (COPs), where a loss functional is minimized over finite configurations of points in a compact domain. While effective in practice, deterministic convergence analyses of greedy-type algorithms are often restrictive and difficult to verify. We propose a stochastic framework in which greedy-type methods are formulated as continuous-time Markov processes on the space of configurations. This viewpoint enables convergence analysis in expectation and in probability under mild structural assumptions on the error functional and the transition kernel. For global error functionals, we derive explicit convergence rates, including logarithmic, polynomial, and exponential decay, depending on an abstract improvement condition. As a pedagogical example, we study stochastic greedy sampling for one-dimensional piecewise linear interpolation and prove exponential convergence of the $L^1$-interpolation error for $C^2$-functions. Motivated by this analysis, we introduce the Randomized Polytope Division Method (R-PDM), a randomized variant of the classical Polytope Division Method, and demonstrate its effectiveness and variance reduction in numerical experiments
comment: 32 pages, 9 figures
☆ Sum of Squares Decompositions and Rank Bounds for Biquadratic Forms
We study positive semi-definite (PSD) biquadratic forms and their sum-of-squares (SOS) representations. For the class of partially symmetric biquadratic forms, we establish necessary and sufficient conditions for positive semi-definiteness and prove that every PSD partially symmetric biquadratic form is a sum of squares of bilinear forms. This extends the known result for fully symmetric biquadratic forms. We describe an efficient computational procedure for constructing SOS decompositions, exploiting the Kronecker-product structure of the associated matrix representation. We present a $2 \times 2$ PSD biquadratic form, and show that it can be expressed as the sum of three squares, but cannot be expressed as the sum of two squares. Furthermore, we present a $3 \times 2$ PSD biquadratic form, and show that it can be expressed as the sum of four squares, but cannot be expressed as the sum of three squares. These show that previously proved results that a $2 \times 2$ PSD biquadratic form can be expressed as the sum of three squares, and a $3 \times 2$ PSD biquadratic form can be expressed as the sum of four squares, are tight.
☆ Stochastic Linear-Quadratic Optimal Control Problems with Markovian Regime Switching and $H_\infty$ Constraint under Partial Information
This paper is concerned with a stochastic linear-quadratic optimal control problem of Markovian regime switching system with model uncertainty and partial information, where the information available to the control is based on a sub-$σ$-algebra of the filtration generated by the underlying Brownian motion and the Markov chain. Based on $H_\infty$ control theory, we turn to deal with a soft-constrained zero-sum linear-quadratic stochastic differential game with Markov chain and partial information. By virtue of the filtering technique, the Riccati equation approach, the method of orthogonal decomposition, and the completion-of-squares method, we obtain the closed-loop saddle point of the zero-sum game via the optimal feedback control-strategy pair. Subsequently, we prove that the corresponding outcome of the closed-loop saddle point satisfies the $H_\infty$ performance criterion. Finally, the obtained theoretical results are applied to a stock market investment problem to further illustrate the practical significance and effectiveness.
comment: 46 pages, 10 figures
♻ ☆ A Class of Optimal Directed Graphs for Network Synchronization
In a paper by Nishikawa and Motter, a quantity called the normalized spread of the Laplacian eigenvalues is used to measure the synchronizability of certain network dynamics. Through simulations, and without theoretical validation, it is conjectured that among all simple directed graphs with a fixed number of vertices and arcs, the optimal value of this quantity is achieved if the Laplacian spectrum satisfies a specific pattern. This paper proves this conjecture and further shows that the conjectured spectral condition is not only sufficient but also necessary. Moreover, the paper proves that the optimal Laplacian spectrum is always achievable by a class of almost regular directed graphs, which can be constructed through an inductive algorithm.
comment: This version proves the conjecture and establishes a stronger statement
♻ ☆ Balanced quasistatic evolutions of critical points in metric spaces
Quasistatic evolutions of critical points of time-dependent energies exhibit piecewise smooth behavior, making them useful for modeling continuum mechanics phenomena like elastic-plasticity and fracture. Traditionally, such evolutions have been derived as vanishing viscosity and inertia limits, leading to balanced viscosity solutions. However, for nonconvex energies, these constructions have been realized in Euclidean spaces and assume non-degenerate critical points. In this paper, we take a different approach by decoupling the time scales of the energy evolution and of the transition to equilibria. Namely, starting from an equilibrium configuration, we let the energy evolve, while keeping frozen the system state; then, we update the state by freezing the energy, while letting the system transit via gradient flow or an approximation of it (e.g., minimizing movement or backward differentiation schemes). This approach has several advantages. It aligns with the physical principle that systems transit through energy-minimizing steady states. It is also fully constructive and computationally implementable, with physical and computational costs governed by appropriate action functionals. Additionally, our analysis is simpler and more general than previous formulations in the literature, as it does not require non-degenerate critical points. Finally, this approach extends to evolutions in locally compact metric path spaces, and our axiomatic presentation allows for various realizations.
comment: 66 pages, 6 figures. Minor adjustments and corrections
♻ ☆ A Note on Piecewise Affine Decision Rules for Robust, Stochastic, and Data-Driven Optimization
Multi-stage decision-making under uncertainty, where decisions are taken under sequentially revealing uncertain problem parameters, is often essential to faithfully model managerial problems. Given the significant computational challenges involved, these problems are typically solved approximately. This short note introduces an algorithmic framework that revisits a popular approximation scheme for multi-stage stochastic programs by Georghiou et al. (2015) and improves upon it to deliver superior policies in the stochastic setting, as well as extend its applicability to robust optimization and a contemporary Wasserstein-based data-driven setting. We demonstrate how the policies of our framework can be computed efficiently, and we present numerical experiments that highlight the benefits of our method.
♻ ☆ Network-Based Optimal Control of Pollution Growth
This paper studies a model for the optimal control (by a centralized economic agent which we call the planner) of pollution diffusion over time and space. The controls are the investments in production and depollution and the goal is to maximize an intertemporal utility function. The main novelty is the fact that the spatial component has a network structure. Moreover, in such a time-space setting we also analyze the trade-off between the use of green or non-green technologies: this also seems to be a novelty in such a setting. Extending methods of previous papers, we can solve explicitly the problem in the case of linear costs of pollution.
♻ ☆ Optimization of Transfers linking Ballistic Captures to Earth-Moon Periodic Orbit Families
The design of transfers to periodic orbits in the Earth-Moon system has regained prominence with NASA's Artemis and CNSA's Chang'e programs. This work addresses the problem of linking ballistic capture trajectories - exploiting multi-body dynamics for temporary lunar orbit insertion - with bounded periodic motion described in the circular restricted three-body problem (CR3BP). A unified framework is developed for optimizing bi-impulsive transfers to families of periodic orbits via a high-order polynomial expansion of the CR3BP dynamics. That same expansion underlies a continuous parameterization of periodic orbit families, enabling rapid targeting and analytic sensitivity. Transfers to planar periodic orbit families - such as Lyapunov L1/L2 and distant retrograde orbits (DROs) - are addressed first, followed by extension to spatial families - such as butterfly and halo L1/L2 orbits - with an emphasis towards near-rectilinear halo orbits (NRHOs). Numerical results demonstrate low-Δv solutions and validate the method's adaptability for designing lunar missions. The optimized trajectories can inform an established low-energy transfer database, enriching it with detailed cost profiles that reflect both transfer feasibility and underlying dynamical relationships to specific periodic orbit families. Finally, the proposed transfers provide reliable estimates for rapid refinement, making them readily adaptable for further optimization across mission-specific needs.
♻ ☆ An overview of the fractional-order gradient descent method and its applications
Recent studies have shown that fractional calculus is an effective alternative mathematical tool in various scientific fields. However, some investigations indicate that results established in differential and integral calculus do not necessarily hold true in fractional calculus. In this work we will compare various methods presented in the literature to improve the Gradient Descent Method, in terms of convergence of the method, convergence to the extreme point, and convergence rate. In general, these methods that generalize the gradient descent algorithm by replacing the gradient with a fractional-order operator are inefficient in achieving convergence to the extremum point of the objective function. To avoid these difficulties, we proposed to choose the Fractional Continuous Time algorithm to generalize the gradient method. In this approach, the convergence of the method to the extreme point of the function is guaranteed by introducing the fractional order in the time derivative, rather than in of the gradient. In this case, the issue of finding the extreme point is resolved, while the issue of stability at the equilibrium point remains.
Fractional Continuous Time method converges to extreme point of cost function when fractional-order is between 0 and 1. The simulations shown in this work suggests that a similar result can be found when $1 \leq α\leq 2$. { This paper highlights the main advantages and disadvantages of generalizations of the gradient method using fractional derivatives, aiming to optimize convergence in complex problems. Some chemical problems, with n=11 and 24 optimization parameters, are employed as means of evaluating the efficacy of the propose algorithms. In general, previous studies are restricted to mathematical questions and simple illustrative examples.
comment: 26 pages, 2 tables, 8 figures
♻ ☆ Asymptotics of motion planning complexity for control-affine systems
In this paper, we study the complexity of the approximation of nonadmissible curves for nonlinear control-affine systems satisfying the strong H{ö}rmander condition. Focusing on tubular approximation complexities, we provide asymptotic equivalences, with explicit constants, for all generic situations where the distribution, i.e., the linear part of the control system, is of co-rank one. Namely, we consider curves in step 2 distributions and any dimension. In the 3 dimensional case, we also consider the case of distributions with Martinet-type singularities that are crossed by the curve at isolated points.
♻ ☆ A universal example for quantitative semi-uniform stability
We characterise quantitative semi-uniform stability for $C_0$-semigroups arising from port-Hamiltonian systems, complementing recent works on exponential and strong stability. With the result, we present a simple universal example class of port-Hamiltonian $C_0$-semigroups exhibiting arbitrary decay rates slower than $t^{-1/2}$.
The latter is based on results from the theory of Diophantine approximation, as the decay rates will be strongly related to the approximation properties of irrational numbers by rationals obtained from cut-offs of continued fraction expansions.
comment: 24 pages; this is version 3, included the proof of Theorem A.5 and fixed an error in proof of Theorem A.6
♻ ☆ Global minimisation of nonconvex functions by generalising the mirror descent method
In this paper we introduce two conceptual algorithms for minimising abstract convex functions. Both algorithms rely on solving a proximal-type subproblem with an abstract Bregman distance based proximal term. We prove their convergence when the set of abstract linear functions forms a linear space. This latter assumption can be relaxed to only require the set of abstract linear functions to be closed under the sum, which is a classical assumption in abstract convexity. We provide numerical examples on the minimisation of nonconvex functions with the presented algorithms.
comment: 15 pages, 3 figures
♻ ☆ A Multiobjective Mathematical Model for Optimal Irrigation Water Allocation
Sustainable irrigation and food security increasingly depend on efficient water resource management in the face of growing climatic and economic constraints. In this study, we develop two single objective optimization models for irrigation planning, one that maximizes net benefit and the other that minimizes environmental flow deficiency, and compare their performance with established models reported in previous studies. We then extend the analysis to a multiobjective programming formulation solved through scalarization and genetic approaches to evaluate trade-offs. Numerical experiments on the Muhuri Irrigation Project reveal three outcomes: (i) a complete scenario view with profits ranging from $ \$ 0.2 \times 10^9$ to $ \$ 1.497\times 10^9$ and environmental flow deficits between 0 and 1200 GL, where the 1200 GL represents the theoretical annual maximum under a 100 GL uniform monthly target; (ii) explicit trade-offs showing higher profits correspond to greater ecological shortfalls; and (iii) an integration based approach producing nearly 1000 Pareto optimal solutions within seconds, greatly outperforming earlier studies.
comment: 25 pages, 1 figure
♻ ☆ Convergence of Sign-based Random Reshuffling Algorithms for Nonconvex Optimization
signSGD is popular in nonconvex optimization due to its communication efficiency. Yet, existing analyses typically assume data are sampled with replacement in each iteration, contradicting a common practical implementation where data are randomly reshuffled and sequentially fed into the algorithm. This gap leaves the theoretical understanding of the more practical algorithm, signSGD with random reshuffling (SignRR), largely unexplored. We develop the first analysis of SignRR to identify the core technical challenge that prevents a thorough convergence analysis of this method. In particular, given a dataset of size $n$ and $T$ epochs, we show that the expected gradient norm of SignRR is upper bounded by $O(\log(nT)/\sqrt{nT} + σ)$, where $σ$ is the averaged conditional mean square error that may not vanish. To tackle this limitation, we develop two new sign-based algorithms under random reshuffling: SignRVR, which incorporates variance-reduced gradients, and SignRVM, which integrates momentum-based updates. Both algorithms achieve a faster convergence rate of ${O}(\log(nT)/\sqrt{nT} +\log(nT)\sqrt{n}/\sqrt{T})$. We further extend our algorithms to a distributed setting, with a convergence rate of ${O}(\log(n_0T)/\sqrt{n_0T} +\log (n_0T)\sqrt{n_0}/\sqrt{T})$, where $n_0$ is the size of the dataset of a single machine. These results mark the first step towards the theoretical understanding of practical implementation of sign-based optimization algorithms. Finally, we back up our theoretical findings through experiments on simulated and real-world problems, verifying that randomly reshuffled sign methods match or surpass existing baselines.
comment: 37 pages, 5 figures